<?php
/**
 * 区间查询检查器 - 详细注释版
 * 
 * 功能：查询指定区间[a,b]与数据库中区间的重叠情况，返回详细的分段结果
 * 
 * 算法核心思想（关键点收集法）：
 * 1. 查询所有与[a,b]重叠的数据库区间
 * 2. 收集所有关键点（区间边界点）
 * 3. 基于关键点创建不重叠的子区间
 * 4. 为每个子区间确定对应的状态
 * 
 * 算法示例：
 * 数据库数据：[1,4]作废, [5,20]正常, [30,40]作废
 * 查询区间：[3, 43]
 * 
 * 步骤1：查询重叠区间 → [1,4], [5,20], [30,40]
 * 步骤2：收集关键点 → [3, 5, 21, 30, 41, 44]
 * 步骤3：创建子区间 → [3,4], [5,20], [21,29], [30,40], [41,43]
 * 步骤4：确定状态 → 作废, 正常, 不存在, 作废, 不存在
 * 
 * 时间复杂度：O(log n + k) 其中n是表中区间数，k是重叠区间数
 * 空间复杂度：O(k) 只存储重叠的区间
 */
class IntervalChecker {
    private $pdo;      // 数据库连接对象
    private $table;    // 要查询的表名
    
    /**
     * 构造函数
     * @param $pdo 数据库连接对象
     * @param string $table 表名，默认为'test'
     */
    public function __construct($pdo, string $table = 'test') {
        $this->pdo = $pdo;
        $this->table = $table;
    }
    
    
    /**
     * 查询与[a, b]区间有重叠的所有记录
     * 
     * 重叠判断公式：两个区间[x1,y1]和[x2,y2]重叠当且仅当 x1 <= y2 AND y1 >= x2
     * 这里查询条件：start_id <= :b AND end_id >= :a
     * 
     * @param int $a 查询区间起始值
     * @param int $b 查询区间结束值
     * @return array 符合条件的区间记录
     */
    public function findOverlappingIntervals(int $a, int $b): array {
        // 构建SQL查询语句
        // 条件说明：
        // - start_id <= :b：数据库区间的开始位置 <= 查询区间的结束位置
        // - end_id >= :a：数据库区间的结束位置 >= 查询区间的开始位置
        // 这两个条件同时满足时，两个区间就有重叠
        $sql = "SELECT start_id, end_id, state
                FROM {$this->table} 
                WHERE start_id <= :b AND end_id >= :a
                ORDER BY start_id";
        
        // 准备SQL语句
        $stmt = $this->pdo->prepare($sql);
        
        // 绑定参数，防止SQL注入
        $stmt->bindParam(':a', $a, PDO::PARAM_INT);
        $stmt->bindParam(':b', $b, PDO::PARAM_INT);
        
        // 执行查询
        $stmt->execute();
        
        // 返回所有匹配的记录
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }
    
    
    /**
     * 检查区间[a, b]在表中的存在情况
     * 
     * 算法步骤：
     * 1. 查询所有与[a,b]重叠的数据库区间
     * 2. 收集所有关键点（区间边界点）
     * 3. 基于关键点创建不重叠的子区间
     * 4. 为每个子区间确定对应的状态
     * 
     * @param int $a 查询区间起始值
     * @param int $b 查询区间结束值
     * @return array 包含各子区间及其状态的数组
     */
    public function checkInterval(int $a, int $b): array {
        // 步骤1：查询所有与[a,b]重叠的数据库区间
        $overlapping = $this->findOverlappingIntervals($a, $b);
        
        // 步骤2：收集所有关键点（区间边界点）
        $points = [];
        $points[] = $a;        // 查询区间的开始点
        $points[] = $b + 1;    // 查询区间的结束点+1（+1是为了确保最后一个点被包含）
        
        // 遍历所有重叠的数据库区间，收集它们的边界点
        foreach ($overlapping as $interval) {
            // 计算与查询区间重叠的部分
            $start = max($interval['start_id'], $a);  // 重叠部分的开始点
            $end = min($interval['end_id'], $b);      // 重叠部分的结束点
            
            // 只有当重叠部分有效时才添加边界点
            if ($start <= $end) {
                $points[] = $start;      // 重叠部分的开始点
                $points[] = $end + 1;    // 重叠部分的结束点+1
            }
        }
        
        // 步骤3：去重并排序关键点
        $points = array_unique($points);  // 去除重复的点
        sort($points);                    // 按从小到大的顺序排序
        
        $result = [];
        
        // 步骤4：基于关键点创建子区间
        for ($i = 0; $i < count($points) - 1; $i++) {
            // 当前子区间的开始和结束点
            $segmentStart = $points[$i];        // 当前关键点
            $segmentEnd = $points[$i + 1] - 1;  // 下一个关键点-1
            
            // 确保子区间在查询范围内
            if ($segmentStart > $b || $segmentEnd < $a) {
                continue;  // 跳过超出查询范围的子区间
            }
            
            // 进一步确保子区间在查询范围内
            $segmentStart = max($segmentStart, $a);
            $segmentEnd = min($segmentEnd, $b);
            
            // 只有当子区间有效时才处理
            if ($segmentStart <= $segmentEnd) {
                // 查找覆盖此子区间的数据库区间
                $coveringInterval = $this->findCoveringInterval($overlapping, $segmentStart, $segmentEnd);
                
                if ($coveringInterval) {
                    // 如果找到覆盖的数据库区间，使用其状态
                    $result[] = [
                        'start' => $segmentStart,
                        'end' => $segmentEnd,
                        'state' => $coveringInterval['state'],
                        'exists' => true
                    ];
                } else {
                    // 如果没有找到覆盖的数据库区间，标记为不存在
                    $result[] = [
                        'start' => $segmentStart,
                        'end' => $segmentEnd,
                        'state' => '不存在表中',
                        'exists' => false
                    ];
                }
            }
        }
        
        return $result;
    }
    
    /**
     * 查找覆盖指定子区间的数据库区间
     * 
     * 判断条件：数据库区间的开始位置 <= 子区间开始位置 且 数据库区间的结束位置 >= 子区间结束位置
     * 即：数据库区间完全包含子区间
     * 
     * @param array $intervals 数据库区间数组
     * @param int $start 子区间开始位置
     * @param int $end 子区间结束位置
     * @return array|null 覆盖的区间，如果没有则返回null
     */
    private function findCoveringInterval(array $intervals, int $start, int $end): ?array {
        // 遍历所有数据库区间
        foreach ($intervals as $interval) {
            // 检查数据库区间是否完全包含子区间
            // 条件：数据库区间的开始 <= 子区间开始 且 数据库区间的结束 >= 子区间结束
            if ($interval['start_id'] <= $start && $interval['end_id'] >= $end) {
                return $interval;  // 找到覆盖的区间，返回它
            }
        }
        return null;  // 没有找到覆盖的区间
    }
    
    
    /**
     * 检查指定区间并返回结果
     * 
     * 这是一个简化的接口方法，调用核心算法并格式化返回结果
     * 
     * @param int $a 查询区间起始值
     * @param int $b 查询区间结束值
     * @return array 包含查询区间和检查结果的数组
     */
    public function check(int $a, int $b): array {
        // 调用核心算法检查区间
        $result = $this->checkInterval($a, $b);
        
        // 格式化返回结果
        return [
            'query_interval' => ['a' => $a, 'b' => $b],  // 查询的区间
            'result' => $result                          // 检查结果
        ];
    }
    
    /**
     * 打印检查结果
     * 
     * 将检查结果以易读的格式输出到控制台
     * 
     * @param array $result 检查结果数组
     */
    public function printResult(array $result): void {
        // 显示查询的区间范围
        echo "查询区间: {$result['query_interval']['a']} ~ {$result['query_interval']['b']}\n\n";
        echo "检查结果:\n";
        
        // 遍历所有子区间，显示每个子区间的状态
        foreach ($result['result'] as $item) {
            echo "{$item['start']}~{$item['end']}：{$item['state']}\n";
        }
    }
}

// ========================================
// 使用示例和测试代码
// ========================================

try {
    // 数据库连接配置
    $host = 'rm-bp1ak55w57hj890mu8o.mysql.rds.aliyuncs.com';
    $dbname = 'baoxian_data';
    $username = 'baoxian';
    $password = 'baoxian@123';
    
    // 创建数据库连接
    // PDO是PHP的数据库抽象层，支持多种数据库
    $pdo = new PDO("mysql:host=$host;dbname=$dbname;charset=utf8", $username, $password);
    
    // 设置错误模式为异常模式，这样数据库错误会抛出异常
    $pdo->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
    
    // 创建区间检查器实例
    // 传入数据库连接对象和表名
    $checker = new IntervalChecker($pdo, 'test');
    
    // 查询区间 [3, 43] 并获取结果
    // 这个区间会与数据库中的多个区间重叠
    $result = $checker->check(3, 43);
    
    // 打印检查结果
    $checker->printResult($result);
    
} catch (PDOException $e) {
    // 捕获数据库连接或查询错误
    die("数据库连接失败: " . $e->getMessage());
} catch (Exception $e) {
    // 捕获其他类型的错误
    die("错误: " . $e->getMessage());
}
?>
